package com.jhy.review.Binarytree;

import java.util.Stack;

/**
 * 递归排序
 * 先序遍历(根左右)
 * 中序遍历（左根右）
 * 后序遍历（左右根）
 */
public class    Traverse {
    // 先序遍历
    public static void preOrderRecur(Tree tree) {

        if (tree == null) {
            return;
        }
        System.out.println(tree.value);
        preOrderRecur(tree.left);
        preOrderRecur(tree.right);

    }

    // 中序遍历
    public static void inOrderRecur(Tree tree) {

        if (tree == null) {
            return;
        }
        preOrderRecur(tree.left);
        System.out.println(tree.value);
        preOrderRecur(tree.right);

    }

    // 后序遍历
    public static void posOrderRecur(Tree tree) {
        if (tree == null) {
            return;
        }
        preOrderRecur(tree.left);
        preOrderRecur(tree.right);
        System.out.println(tree.value);


    }

    /**
     * 非递归的方式来实现
     * 先序
     * 用栈来实现
     * <p>
     * (1) 弹出节点
     * (2) 打印
     * (3) 右不为空就右 左不为空 就进左
     */
    public static void preOrderUnRecur(Tree tree) {
        if (tree != null) {
            // 先创建一个栈 然后将头节点入栈
            Stack<Tree> stack = new Stack<Tree>();
            stack.push(tree);
            while (!stack.isEmpty()) {
                stack.pop();
                System.out.println(tree.value + "");
                if (tree.right != null) {
                    stack.push(tree.right);
                }
                if (tree.left != null) {
                    stack.push(tree.left);
                }
            }
        }
        System.out.println();
    }
    // 后序遍历
    public static void posOrderUnRecur2(Tree tree) {
        if (tree != null) {
            Stack<Tree> s1 = new Stack<Tree>();
            Stack<Tree> s2 = new Stack<Tree>();
            s1.push(tree);
            // 循环遍历s1数组
            while (!s1.isEmpty()) {
                // 弹出当前的节点
                tree = s1.pop();
                // 将弹出的节点放入到另外一个栈当中
                s2.push(tree);
                if (tree.right != null) {
                    s2.push(tree.right);
                }
                if (tree.left != null) {
                    s2.push(tree.left);
                }
            }
            while (!s2.isEmpty()) {
                System.out.println(s2.pop().value);
            }
        }
        System.out.println();
    }
    // 中序遍历 非递归的方式 都是对头节点进行操作
    public static void  inOrderUnRecur(Tree tree){
        if(tree != null){
            Stack<Tree> stack = new Stack<>();
            while(!stack.isEmpty() || tree != null){
                if(tree != null){
                    // 先将子树的头节点和左边界全部依次入栈
                    stack.push(tree);
                    tree = tree.left;
                    // 直到左边界的下一个为null的时候停止
                }else {
                    // 依次弹出节点
                    tree = stack.pop();
                    // 并打印
                    System.out.println(tree.value+"");
                    // 然后转到右树并对左边界进行重复操作  相当于是左根右（右 => 左根右）
                    tree = tree.right;
                }
            }
        }
        System.out.println();
    }
}
